home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / bi_matching.c next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.4 KB  |  77 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. main()
  6. {
  7.  
  8. GRAPH<int,int> G;
  9. list<node> A,B;
  10. edge e;
  11.  
  12. test_bigraph(G,A,B);
  13.  
  14. edge_array<int>  weight1(G);
  15.  
  16.  
  17. init_random();
  18.  
  19. forall_edges(e,G) G[e] = weight1[e] =  random(0,1000);
  20.  
  21.  
  22.  
  23. if (Yes("show graph? ")) G.print();
  24.  
  25. float T = used_time();
  26.  
  27. cout << "MAX_CARD_BIPARTITE MATCHING            ";
  28. cout.flush();
  29. list<edge> M0 = MAX_CARD_BIPARTITE_MATCHING(G,A,B);
  30. cout << string("%5.2f sec    |M| = %d\n",used_time(T), M0.length());
  31.  
  32. /*
  33. if (Yes("output ? "))  
  34.    { newline;
  35.      forall(e,M0) { G.print_edge(e); newline; }
  36.      newline;
  37.     }
  38. */
  39.  
  40. cout << "MAX_CARD_MATCHING                      ";
  41. cout.flush();
  42. list<edge> M1 = MAX_CARD_MATCHING(G);
  43. cout << string("%5.2f sec    |M| = %d\n",used_time(T), M1.length());
  44.  
  45. /*
  46. if (Yes("output ? "))  
  47.    { newline;
  48.      forall(e,M1) { G.print_edge(e); newline; }
  49.      newline;
  50.     }
  51. */
  52.  
  53. newline;
  54.  
  55. int w = 0;
  56.  
  57. cout << "MAX_WEIGHT_BIPARTITE_MATCHING <int>    ";
  58. cout.flush();
  59. list<edge> M2 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight1);
  60. forall(e,M2)  w += weight1[e];
  61. cout << string("%5.2f sec   W = %d\n",used_time(T),w);
  62.  
  63. double W = 0;
  64.  
  65. edge_array<double> weight2(G);
  66.  
  67. forall_edges(e,G) weight2[e] =  weight1[e]/1000.0; 
  68.  
  69. cout << "MAX_WEIGHT_BIPARTITE_MATCHING <double> ";
  70. cout.flush();
  71. list<edge> M3 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight2);
  72. forall(e,M3)  W += weight2[e];
  73. cout << string("%5.2f sec   W = %.2f\n",used_time(T),W);
  74.  
  75. return 0;
  76. }
  77.